Search results for "Consensus algorithm"
showing 10 items of 12 documents
A greedy perturbation approach to accelerating consensus algorithms and reducing its power consumption
2011
The average consensus is part of a family of algorithms that are able to compute global statistics by only using local data. This capability makes these algorithms interesting for applications in which these distributed philosophy is necessary. However, its iterative nature usually leads to a large power consumption due to the repetitive communications among the iterations. This drawback highlights the necessity of minimizing the power consumption until consensus is reached. In this work, we propose a greedy approach to perturbing the connectivity graph, in order to improve the convergence time of the consensus algorithm while keeping bounded the power consumption per iteration step. These …
Convergence Analysis of Distributed Set-Valued Information Systems
2016
This paper focuses on the convergence of information in distributed systems of agents communicating over a network. The information on which the convergence is sought is not rep- resented by real numbers, as often in the literature, rather by sets. The dynamics of the evolution of information across the net- work is accordingly described by set-valued iterative maps. While the study of convergence of set-valued iterative maps is highly complex in general, this paper focuses on Boolean maps, which are comprised of arbitrary combinations of unions, intersections, and complements of sets. For these important class of systems, we provide tools to study both global and local convergence. A distr…
Set-valued consensus for distributed clock synchronization
2009
This paper addresses the clock synchronization problem in a wireless sensor network (WSN) and proposes a distributed solution that consists of a form of consensus, where agents are able to exchange data representing intervals or sets. The solution is based on a centralized algorithm for clock synchronization, proposed by Marzullo, that determines the smallest interval that is in common with the maximum number of measured intervals. We first show how to convert such an algorithm into a problem involving only operations on sets, and then we convert it into a set–valued consensus. The solution is valid for more general scenarios where agents have uncertain measures of e.g. the position of an o…
Distributed Consensus on Boolean Information
2009
Abstract In this paper we study the convergence towards consensus on information in a distributed system of agents communicating over a network. The particularity of this study is that the information on which the consensus is seeked is not represented by real numbers, rather by logical values or sets. Whereas the problems of allowing a network of agents to reach a consensus on logical functions of input events, and that of agreeing on set–valued information, have been separately addressed in previous work, in this paper we show that these problems can indeed be attacked in a unified way in the framework of Boolean distributed information systems. Based on a notion of contractivity for Bool…
Logical Consensus for Distributed Network Agreement
2008
In this paper we introduce a novel consensus mechanism where agents of a network are able to share logical values, or Booleans, representing their local opinions on e.g. the presence of an intruder or of a fire within an indoor environment. Under suitable joint conditions on agents? visibility and communication capability, we provide an algorithm generating a logical linear consensus system that is globally stable. The solution is optimal in terms of the number of messages to be exchanged and the time needed to reach a consensus. Moreover, to cope with possible sensor failure, we propose a second design approach that produces robust logical nonlinear consensus systems tolerating a maximum n…
Consensus-based Distributed Intrusion Detection for Multi-Robot Systems
2008
This paper addresses a security problem in robotic multi-agent systems, where agents are supposed to cooperate according to a shared protocol. A distributed Intrusion Detection System (IDS) is proposed here, that detects possible non-cooperative agents. Previous work by the authors showed how single monitors embedded on-board the agents can detect non- cooperative behavior, using only locally available information. In this paper, we allow such monitors to share the collected information in order to overcome their sensing limitation. In this perspective, we show how an agreement on the type of behavior of a target-robot may be reached by the monitors, through execution of a suitable consensu…
A self-routing protocol for distributed consensus on logical information
2010
In this paper, we address decision making problems, depending on a set of input events, with networks of dynamic agents that have partial visibility of such events. Previous work by the authors proposed so-called logical consensus approach, by which a network of agents, that can exchange binary values representing their local estimates of the events, is able to reach a unique and consistent decision. The approach therein proposed is based on the construction of an iterative map, whose computation is centralized and guaranteed under suitable conditions on the input visibility and graph connectivity. Under the same conditions, we extend the approach in this work by allowing the construction o…
Decentralized unscented Kalman filter based on a consensus algorithm for multi-area dynamic state estimation in power systems
2015
Abstract A decentralized unscented Kalman filter (UKF) method based on a consensus algorithm for multi-area power system dynamic state estimation is presented in this paper. The overall system is split into a certain number of non-overlapping areas. Firstly, each area executes its own dynamic state estimation based on local measurements by using the UKF. Next, the consensus algorithm is required to perform only local communications between neighboring areas to diffuse local state information. Finally, according to the global state information obtained by the consensus algorithm, the UKF is run again for each area. Its performance is compared with the distributed UKF without consensus algori…
Distributed n-player approachability via time and space average consensus
2012
Abstract In this paper we consider repeated coalitional games with transferable utilities (TU) over networks. Namely, we consider a set of n players that have to distribute among themselves a vector of rewards (one for each player). In our network version there is no coordinator allocating the rewards, but the agents have to agree on a common time-averaged vector by updating the local estimates of the reward vector. The common time-averaged reward vector has to approach a suitable constraint set, called core of the game, that guarantees that no agents benefit from quitting the grand coalition. We propose a doubly (over time and space) averaging distributed algorithm. At every iteration, eac…
On the Robust Synthesis of Logical Consensus Algorithms for Distributed Intrusion Detection
2013
We introduce a novel consensus mechanism by which the agents of a network can reach an agreement on the value of a shared logical vector function depending on binary input events. Based on results on the convergence of finite--state iteration systems, we provide a technique to design logical consensus systems that minimize the number of messages to be exchanged and the number of steps before consensus is reached, and that can tolerate a bounded number of failed or malicious agents. We provide sufficient joint conditions on the input visibility and the communication topology for the method's applicability. We describe the application of our method to two distributed network intrusion detecti…